// ConsoleApplication4.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include <iostream>
#include <time.h>
#include <vector>
using namespace std;

vector<int> bubbleSort(vector<int> Num)
{
	for (int i = 0; i < Num.size(); i++)
	{
		for (int j = i+1; j < Num.size(); j++)
		{
			if (Num[i] > Num[j])
			{
				int temp = Num[i];
				Num[i] = Num[j];
				Num[j] = temp;
			}
		}
	}
	return Num;
}

vector<int> selectSort(vector<int> Num)
{
	for (int i = 0; i < Num.size(); i++)
	{
		int Index = i;
		for (int j = i + 1; j < Num.size(); j++)
		{
			if (Num[j] < Num[Index])
			{
				Index = j;
			}
		}
		if (Index != i)
		{
			int temp = Num[Index];
			Num[Index] = Num[i];
			Num[i] = temp;
		}
	}
	return Num;
}

vector<int> insertSort(vector<int> Num)
{
	for (int i=0; i < Num.size() - 1; i++)
	{
		for (int j = i + 1; j > 0; j--)
		{
			if (Num[j] < Num[j-1])
			{
				int tmp = Num[j];
				Num[j] = Num[j-1];
				Num[j-1] = tmp;
			}
			else
				break;
		}
	}
	return Num;
}

vector<int> shellSort(vector<int> Num)
{
	int incre = Num.size();
	while (incre!=0)
	{
		incre /= 2;
		for (int i = 0; i < incre; i++)
		{
			for (int j = i; j < Num.size()- incre; j += incre)
			{
				for (int k = j + incre; k > i; k -= incre)
				{
					if (Num[k] < Num[k - incre])
					{
						int tmp = Num[k];
						Num[k] = Num[k - incre];
						Num[k - incre] = tmp;
					}
					else
						break;
				}
			}
		}
	}
	return Num;
}


vector<int> quickSort(vector<int> & Num, int l, int r)
{
    if (l >= r) return Num;
	int key = Num[l];
	int orl = l, orr = r;
	while (l < r)
	{
		while (l<r&&Num[r] > key)
		{
			r--;
		}
		if (l < r)
		{
			Num[l] = Num[r];
			l++;
		}
		while (l<r&&Num[l] < key)
		{
			l++;
		}
		if (l < r)
		{
			Num[r] = Num[l];
			r--;
		}
	}
	Num[l] = key;
	quickSort(Num, orl, l-1);
	quickSort(Num, r+1, orr);
	return Num;
}

vector<int> mergeSort(vector<int>& input, int left, int right, vector<int>& output)
{
	if (left >= right) return output;
	int middle = (left + right) / 2;//由于除法取整，会舍掉小数部分，故四个数时是3/2=1=middle,第一个序列为0，1，第二个序列为2,3
	mergeSort(input, left, middle, output);
	mergeSort(input, middle+1, right, output);
	int i = left, j = middle+1,k=left;//由上条注释说明，j=middle+1符合归并规则
	while (i <= middle&&j <= right)
	{
		if (input[i] < input[j])
		{
			output[k++] = input[i++];
		}
		else
		{
			output[k++] = input[j++];
		}
	}
	while (i <= middle)
	{
		output[k++] = input[i++];
	}
	while (j <= right)
	{
		output[k++] = input[j++];
	}
	for (int t = left; t <= right; t++)
	{
		input[t] = output[t];
	}
	return output;
}



int main()
{
	vector<int> test = { 5,2,3,8,9,4,55,6,9,5,2,11,4,55,6,54,0};
	//vector<int> result = bubbleSort(test);
	//vector<int> result = selectSort(test);
	//vector<int> result = insertSort(test);
	//vector<int> result = shellSort(test);
	//vector<int> result = quickSort(test, 0, test.size() - 1);
	vector<int> tmp(test);
	vector<int> result = mergeSort(test, 0, test.size() - 1, tmp);
	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i] << endl;
	}
}

